#pragma once
#include <iostream>
#include "reve_iterator.hpp"
using namespace std;
namespace cc
{
 //链表节点
 template<class T>
 struct ListNode
 {
    T _val;
    ListNode *_next;
    ListNode *_prev;
    ListNode(const T& x=T())
        : _val(x)
        , _next(nullptr)
        , _prev(nullptr)
    {}
 }; 
 //迭代器
 template<class T,class ref,class ptr>
 struct list_iterator
 {
    typedef ListNode<T> Node;
    typedef list_iterator<T,ref,ptr> iterator;
    list_iterator(Node *node)
        : _node(node)
    {}
    iterator& operator++()
    {
        _node=_node->_next;
        return *this;
    }
    iterator operator++(int)
    {
        iterator tem(_node);
        _node=_node->_next;
        return tem;
    }
    iterator& operator++()const
    {
        _node=_node->_next;
        return *this;
    }
    iterator operator++(int)const
    {
        iterator tem(_node);
        _node=_node->_next;
        return tem;
    }
    iterator& operator--()
    {
        _node=_node->_prev;
        return *this;
    }
    iterator operator--(int)
    {
        iterator tem(_node);
        _node=_node->_prev;
        return tem;
    }
    bool operator!=(const iterator& d)const
    {
        return _node!=d._node;
    }
    ref operator*()const
    {
        return _node->_val;
    }
    ptr operator->()const
    {
        return &(_node->_val);
    }
    Node *_node;
 };
 //链表
 template<class T>
 class List
 {
public:
    typedef ListNode<T> Node;
    typedef list_iterator<T,T&,T*> iterator;
    typedef list_iterator<T,const T&,const T*> const_iterator;
    typedef reve_iterator<iterator,T&,T*> riterator;
    typedef reve_iterator<iterator,const T&,const T*> const_riterator;
    void init()
    {
        _head->_next=_head;
        _head->_prev=_head;
    }
    List()
        : _head(new Node)
    {
        _head->_next=_head;
        _head->_prev=_head;
    }
    template<typename Iterator>
    List(Iterator begin,Iterator end)
        : _head(new Node)
    {
        init();
        while(begin!=end)
        {
            push_back(*begin);
            begin++;
        }
    }
    List(const List<T>& d)
        : _head(nullptr)
    {
        List<T> tem(d.begin(),d.end());
        swap(tem);
    }
    List<T>& operator=(List<T> d)
    {
        swap(d);
        return *this;
    }
    iterator begin()
    {
        return iterator(_head->_next);
    }
    iterator end()
    {
        return iterator(_head);
    }
    riterator rbegin()
    {
        return riterator(_head);
    }
    riterator rend()
    {
        return riterator(_head->_next);
    }
    const_iterator begin()const
    {
        return const_iterator(_head->_next);
    }
    const_iterator end()const
    {
        return const_iterator(_head);
    }
    void swap(List<T>& d)
    {
        std::swap(_head,d._head);
    }
    void push_back(const T& x=T())
    {
        Node *cur=new Node(x);
        Node *tail=_head->_prev;
        tail->_next=cur;
        cur->_prev=tail;
        cur->_next=_head;
        _head->_prev=cur;
    }
private:
    Node *_head;
 };
}